|
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity. An ancient precursor is the Sanskrit treatise Shulba Sutras , or "Rules of the Chord", that is a book of algorithms written in 800 BCE. The book prescribes step-by-step procedures for constructing geometric objects like altars using a peg and chord. Computational complexity is central to computational geometry, with great practical significance if algorithms are used on very large datasets containing tens or hundreds of millions of points. For such sets, the difference between O(''n''2) and O(''n'' log ''n'') may be the difference between days and seconds of computation. The main impetus for the development of computational geometry as a discipline was progress in computer graphics and computer-aided design and manufacturing (CAD/CAM), but many problems in computational geometry are classical in nature, and may come from mathematical visualization. Other important applications of computational geometry include robotics (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (mesh generation), computer vision (3D reconstruction). The main branches of computational geometry are: *''Combinatorial computational geometry'', also called ''algorithmic geometry'', which deals with geometric objects as discrete entities. A groundlaying book in the subject by Preparata and Shamos dates the first use of the term "computational geometry" in this sense by 1975. * ''Numerical computational geometry'', also called ''machine geometry'', ''computer-aided geometric design'' (CAGD), or ''geometric modeling'', which deals primarily with representing real-world objects in forms suitable for computer computations in CAD/CAM systems. This branch may be seen as a further development of descriptive geometry and is often considered a branch of computer graphics or CAD. The term "computational geometry" in this meaning has been in use since 1971.〔A.R. Forrest, "Computational geometry", ''Proc. Royal Society London'', 321, series 4, 187-195 (1971)〕 == Combinatorial computational geometry == The primary goal of research in combinatorial computational geometry is to develop efficient algorithms and data structures for solving problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc. Some of these problems seem so simple that they were not regarded as problems at all until the advent of computers. Consider, for example, the ''Closest pair problem'': * Given ''n'' points in the plane, find the two with the smallest distance from each other. One could compute the distances between all the pairs of points, of which there are ''n(n-1)/2'', then pick the pair with the smallest distance. This brute-force algorithm takes O(''n''2) time; i.e. its execution time is proportional to the square of the number of points. A classic result in computational geometry was the formulation of an algorithm that takes O(''n'' log ''n''). Randomized algorithms that take O(''n'') expected time,〔S. Khuller and Y. Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1):34—37,1995〕 as well as a deterministic algorithm that takes O(''n'' log log ''n'') time,〔S. Fortune and J.E. Hopcroft. "A note on Rabin's nearest-neighbor algorithm." Information Processing Letters, 8(1), pp. 20—23, 1979〕 have also been discovered. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Computational geometry」の詳細全文を読む スポンサード リンク
|